import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class code2 {
//    三数之和
public List<List<Integer>> threeSum(int[] nums) {
    // 这道题目需要找到三个符合题意的数据
    // 根据题目我们可知 first + second + third = 0
    // 我们可以将这个式子进行简单的优化操作，便于我们的编码计算
    // 可以将上述式子转换为 second + third = -first
    int len = nums.length;

    // 因为返回的要求是数组中的数字又不是下标
    // 所以为了便于计算，这里需要将 nums 中的数据先进行一下排序操作
    Arrays.sort(nums);
    // 创建出一个链表用于记录返回值
    List<List<Integer>> re = new ArrayList<>();

    // 首先通过最外层的 for 循环控制在数组头部的数字即 first
    for (int first = 0; first < len; first++) {
        // 因为在数组中是存在重复数字的，所以这里需要现将重复的数字进行排除
        // 因为是要将当前的值和上一个位置的值进行比较，所以这里的 first 值是有一个必须大于 0 的先决条件
        if (first > 0 && nums[first] == nums[first - 1]) {
            continue;
        }
        // 当运行到这里，就说明已经选中了 first
        // 直接将 first 转换为 - 数
        int flag = -nums[first];
        // 在这里定义 thrid 就是为了在外部循环跟新 first 时
        // 同时更新 third 处于最后一个位置
        int third = len - 1;

        // 在来一个 for 循环，这个是用来记录 first 后面的合理的数据的
        for (int second = first + 1; second < len; second++) {
            // 同样的，这里也要让每一次的值不能和前一个位置上的值相同
            if (second > first + 1 && nums[second] == nums[second - 1]) {
                continue;
            }
            // 这里需要将 second 和 third 进行相加比较
            // 如果说两者相加的值 > flag 这就说明 thrid 不符合条件
            while (second < third && nums[second] + nums[third] > flag) {
                third--;
            }
            // 当出现指针重合后，此时就直接退出循环
            if (second == third) {
                break;
            }
            // 判断当second + third = flag 时，说明符合条件
            if (nums[second] + nums[third] == flag) {
                List<Integer> list = new ArrayList<>();
                list.add(nums[first]);
                list.add(nums[second]);
                list.add(nums[third]);
                ;
                re.add(list);
            }
        }
    }
    return re;
}
}
